package version1;

/**
 * kmp算法
 *
 * @author zhangjiayuan@qipeipu.com
 * @date 2019/1/8 20:10
 * @since 1.0.0
 */
public class Violence {
    /**
     * 传统解法
     *
     * @param ts 主串
     * @param ps 从串
     * @return
     */
    public static int kmp(String ts, String ps) {
        char[] tsChar = ts.toCharArray();
        char[] psChar = ps.toCharArray();
        int i = 0;  //主串的位置
        int j = 0;  //模式串的位置
        while (i < tsChar.length && j < psChar.length) {
            if (tsChar[i] == psChar[j]) {   //若比较的字符相同，则比较下一个
                i++;
                j++;
            } else {
                i = i - j + 1;  //不匹配时，i回溯，j回溯
                j = 0;
            }
        }
        if (j == psChar.length) {
            return i - j;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        String ts = "abcdabcdababcdabcdababcdabcdabcde";
        String ps = "abcde";
        long begin = System.nanoTime();
        int result = Violence.kmp(ts, ps);
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println(end-begin);
    }
}
